import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 图表结构： （1）图是一种数据结构，用于表示 “多对多” 的关系
 *          （2）底层实现可以是“二维数组”（邻接矩阵），也可以是“一维数组 + 链表”（邻接表）
 *          （3）分有向图，无向图
 *          （4）节点：就是图中一个顶点的意思
 *          （5）邻接：表示图结构中，A节点与B节点之间，可以不通过其他节点，就能直接到达的意思。
 *
 *  手动实现一个图结构：利用邻接矩阵实现
 *      1.创建一个集合用于存储，图中所有的节点；是什么类型的数据节点，就用什么类型的集合进行存储
 *      2.创建一个二维数组：存储图中，节点与节点之间的是否邻接，默认0表示不邻接，1表示邻接
 *          二维数组中某行：就表示某个节点元素，这一行中的各个值，就表示该节点与其他节点之间的邻接关系，跟本身节点的邻接关系，都是默认0
 */
public class Graph {
    private ArrayList<String> vertexList;   //创建一个集合,用于存储图中的各个顶点,顶点数据是String类型
    private int[][] edges;   //创建一个二维数组，表示对应的邻接矩阵
    private int numsOfEdges;    //表示顶点与顶点之间边的数量
    private boolean[] isVisit;  //图的深度优先遍历算法需要使用的布尔数组，用于存放每个节点的标记。表示某个节点，是否被访问过，true表示已访问，false表示未访问
    private boolean[] isVisit2;  //图的广度优先遍历算法需要使用的布尔数组，用于存放每个节点的标记。表示某个节点，是否被访问过，true表示已访问，false表示未访问

    public static void main(String[] args) {
        int n = 5; //节点个数
        String[] vertexValue = {"A", "B", "C", "D", "E"};//需要添加的数据
        //创建一个图
        Graph graph = new Graph(n);
        //给图添加节点
        for (String s : vertexValue) {
            graph.insertVertex(s);
        }
        // 添加边 A-B A-C B-C B-D B-E
        graph.insertEdge(0,1,1);//A-B
        graph.insertEdge(0,2,1);//A-C
        graph.insertEdge(1,2,1);//B-C
        graph.insertEdge(1,3,1);//B-D
        graph.insertEdge(1,4,1);//B-E
        //打印边的数量
        System.out.println("图总共的边："+graph.getNumsOfEdges());
        //打印图对应矩阵
        graph.showGraph();
        System.out.println("----------------");
        //调用深度优先遍历算法
        System.out.println("深度优先遍历:");
        graph.dfs();//A->B->C->D->E->
        System.out.println();
        System.out.println("----------------");
        //调用广度优先遍历算法
        System.out.println("广度优先遍历:");
        graph.bfs();//A->B->C->D->E->
    }

    /**
     * 创建构造方法，进行初始化
     * n : 创建有多少个节点（节点，又称顶点）的图
     */
    public Graph(int n) {
        this.vertexList = new ArrayList<>(n);//初始化集合，表示有n个元素
        this.edges = new int[n][n];//初始化矩阵，
        this.isVisit = new boolean[n];//初始化标记访问数组，长度就是图中节点的数量，每一个值都是与节点相对应
        this.isVisit2 = new boolean[n];//初始化标记访问数组，长度就是图中节点的数量，每一个值都是与节点相对应
        this.numsOfEdges = 0;//默认为0
    }

    /**
     * 根据传入的二维数组行索引，求该节点的第一个邻接点的数组下标（列值），“该邻接点的行索引”与“传入的二维数组行索引”保持不变
     * 注意：一个行索引：就表示一个节点元素
     * @param index:传入的行索引，默认是从0开始，因为0在对应的二维数组中，就表示图对应的第一个节点元素
     * @return ：返回该节点的第一个邻接点的数组下标
     */
    public int getFirstNeighbor(int index){
        //遍历整个当前节点的所有邻接点，获取在二维数组中存放的第一个邻接点
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;//返回的是列值下标
            }
        }
        //没找到返回-1
        return -1;
    }

    /**
     * 根据前一个邻接点的数组下标，获取“前一个邻接点的邻接点”数组下标，行索引与第一个邻接点保持不变
     * @param v1:前一个邻接点的行索引，也是刚开始传入的二维数组索引
     * @param v2:前一个邻接点的列索引
     * @return :前一个邻接点的邻接点数组下标
     */
    public int getNextNeighbor(int v1,int v2){
        //从第 “v1”行， “v2+1” 列开始遍历，直到找到下一个邻接点
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                //若找到下一个邻接点，则返回对应的列值，该列值也是该邻接点的对应所在的行值
                return i;
            }
        }
        //没有找到，则返回-1
        return -1;
    }

    /**
     * 深度优先遍历算法（depthFirstSearch）：
     * 以传入的索引值为开始节点，以深度优先遍历算法，依次输出每个节点邻接的第一个节点。
     *  注意：1.若是该节点之前的的节点，无法遍历输出
     *      2.若后面有些节点，是该节点之前的节点才能邻接的节点，无法遍历输出
     * @param index:传入的索引值
     */
    public void dfs(boolean[] isVisit, int index){
        //先输出当前节点的值
        System.out.print(getValueByIndex(index) + "->");
        //将当前输出的节点，标记为已访问
        isVisit[index] = true;
        //获取当前节点的第一个邻接点的行索引
        int w = getFirstNeighbor(index);
        //判断第一个邻接点，是否存在
        while (w != -1){//不等于-1，就表示存在第一个邻接点
            //判断这个邻接点，是否访问过
            if (!isVisit[w]) {
                //若没有访问过，则递归调用当前方法
                dfs(isVisit,w);
            }
            //若已经访问过，则获取前一个邻接点的邻接点
            w = getNextNeighbor(index,w);//将第二个邻接点赋给第一个邻接点变量，遍历循环要用
        }
        //若该邻接点不存在,则结束方法
    }

    /**
     * 重载“深度优先遍历”算法，回溯调用dfs方法
     * 且必须循环每一个节点（行索引），不然可能会有某些特殊节点无法被遍历到
     */
    public void dfs(){
        //循环每一个节点,即，每一个行索引
        for (int i = 0; i < vertexList.size(); i++) {
            //若当前节点已经被输出，则直接进行下一个循环
            if (!isVisit[i]) {
                dfs(isVisit,i);
            }
        }
    }

    /**
     * 图的广度优先遍历算法
     * @param isVisit2：标记数组
     * @param index：传入的的二维数组行索引
     */
    public void bfs(boolean[] isVisit2,int index){
        int u; // 表示队列的头结点的下标
        int w; // 邻接节点的下标
        LinkedList<Integer> queue = new LinkedList<>();//利用双链表集合，当作一个队列使用，图的广度优先遍历算法需要使用
        //访问初始节点
        System.out.print(getValueByIndex(index) + "->");//从集合中输出第一个元素
        //标记已访问
        isVisit2[index] = true;
        //当前已访问节点的索引，放入队列
        queue.addLast(index);
        //根据队列是否为空，继续执行
        while (!queue.isEmpty()){//队列非空，执行里面内容
            //获取队列第一个节点的行索引
            u = queue.removeFirst();
            //获取当前节点的第一邻接点的行索引
            w = getFirstNeighbor(u);//注意：一个节点的行索引与列索引是相等
            while (w != -1){//第一邻接点不为空
                if (!isVisit2[w]) {//该邻接点没有被访问过
                    System.out.print(getValueByIndex(w) + "->");
                    isVisit2[w] = true;
                    // 入队列
                    queue.addLast(w);
                }
                // 已经访问过的话，获取当前取出队列节点的下一个邻接点， 以u为为前驱 找 w 的下一个邻接结点
                w = getNextNeighbor(u,w); // 体现出广度优先
            }
        }
    }

    /**
     * 重载广度优先遍历算法，方便调用
     *  遍历所有的节点 都进行广度优先搜索
     */
    public void bfs() {
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisit2[i]) {
                bfs(isVisit2, i);
            }
        }
    }


    /**
     *  图的常用方法
     */
    //1.返回节点的个数
    public int getNumOfVertex(){
        return vertexList.size();
    }

    //2.得到边的数目
    public int getNumsOfEdges(){
        return numsOfEdges;
    }

    //3.返回某个节点索引，对应的数据
    public String getValueByIndex(int index){
        return vertexList.get(index);
    }

    //4.返回v1 和 v2 边的权值
    public int getEdgeValue(int v1,int v2){
        return edges[v1][v2];
    }

    //5.显示图对应的矩阵
    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    //创建插入节点的方法,将节点放入集合中去
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 添加边的方法
     * @param v1:当前顶点的下标
     * @param v2：当前顶点的某个邻近顶点的下标
     * @param weight:边的权值，即，当前顶点，能不能指向，当前顶点的某个邻近顶点; 0表示不能，1表示能
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numsOfEdges++;//边数量加一
    }
}
